package Test1;

import java.util.ArrayList;
import java.util.List;

class BSTNode<T extends Comparable<T>>{
    private T data;
    private BSTNode<T> left;
    private BSTNode<T> right;

    public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BSTNode<T> getLeft() {
        return left;
    }

    public void setLeft(BSTNode<T> left) {
        this.left = left;
    }

    public BSTNode<T> getRight() {
        return right;
    }

    public void setRight(BSTNode<T> right) {
        this.right = right;
    }
}

class BSTN<T extends  Comparable<T>> {
    private BSTNode<T> root;

    public BSTN() {
        this.root = null;
    }
    //非递归实现插入节点
    public void non_insert(T data){
        // 1.判断如果root是null，如果root是null，直接生成根节点，让root指向，结束
        if(root == null){
            this.root = new BSTNode<>(data, null, null);
            return;
        }
        // 2.如果root不为空，从根节点开始搜索一个合适的位置
        BSTNode<T> cur = this.root;
        BSTNode<T> parent = null; // this.root
        while(cur != null){
            if(cur.getData().compareTo(data) > 0){
                parent = cur;
                cur = cur.getLeft();
            } else if(cur.getData().compareTo(data) < 0){
                parent = cur;
                cur = cur.getRight();
            } else {
                return;
            }
        }
        // 3.生成新节点，把节点的地址，写入父节点相应的地址域
        if(parent.getData().compareTo(data) > 0){
            parent.setLeft(new BSTNode<T>(data, null, null));
        } else {
            parent.setRight(new BSTNode<T>(data, null, null));
        }
    }

    public void non_remove(T data) {
        // 1. 先搜索BST树，找到待删除的节点
        BSTNode<T> cur = root;
        BSTNode<T> parent = null;
        while (cur != null) {
            if(cur.getData().compareTo(data) < 0) {
                parent = cur;
                cur = cur.getRight();
            } else if(cur.getData().compareTo(data) > 0) {
                parent = cur;
                cur = cur.getLeft();
            } else {
                //找到，跳出循环
                break;
            }
        }
        if(cur==null) {
            //找到最下层为null时返回，说明没有找到
            System.out.println("no found!");
            return;
        }
        // 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，删除前驱节点
        if(cur.getLeft()!=null && cur.getRight()!=null) {
            BSTNode<T> old = cur;
            parent = cur;
            cur = cur.getLeft();
            while(cur.getRight()!=null) {
                parent = cur;
                cur = cur.getRight();
            }
            old.setData(cur.getData());
        }
        // 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）
        //如果进入了情况2，那么这里应该删除的是前驱节点
        //综合起来，这里需要删除cur节点
        BSTNode<T> child = cur.getLeft();
        if(child==null) {
            child=cur.getRight();
        }
        if(parent==null) {
            root = child;
        } else {
            if(parent.getLeft()==cur) {
                parent.setLeft(child);
            } else {
                parent.setRight(child);
            }
        }
    }
    public boolean non_query(T data){
        BSTNode<T> cur = this.root;
        while(cur != null) {
            if(cur.getData().compareTo(data) > 0){
                cur = cur.getLeft();
            } else if(cur.getData().compareTo(data) < 0){
                cur = cur.getRight();
            } else {
                return true;
            }
        }
        return false;
    }
    public void preOrder() {
        System.out.print("Preorder traversal :");
        preOrder(root);
    }

    private void preOrder(BSTNode<T> root) {
        if(root!=null) {
            System.out.print(root.getData()+" ");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }

    public void inOrder() {
        System.out.print("In-order traversal:");
        inOrder(root);
    }

    private void inOrder(BSTNode<T> root) {
        if(root!=null) {
            inOrder(root.getLeft());
            System.out.print(root.getData()+" ");
            inOrder(root.getRight());
        }
    }
    public int level() {
        return level(root);
    }

    private int level(BSTNode<T> node) {
        if(node != null) {
            int left = level(node.getLeft());
            int right = level(node.getRight());
            //当前节点的高度是左子树和右子树较大的高度加1
            return Math.max(left,right) + 1;
        }
        return 0;
    }

    public void levelOrder() {
        int hight = level();
        for (int i = 0; i < hight; i++) {
            levelOrder(root,i);
        }
    }

    private void levelOrder(BSTNode<T> root,int level) {
        if(root!= null) {
            if(level==0) {
                System.out.print(root.getData()+" ");
            }
            levelOrder(root.getLeft(),level-1);
            levelOrder(root.getRight(),level-1);
        }
    }


    public int number() {
        return number(root);
    }

    private int number(BSTNode<T> node) {
        if(node!=null) {
            return number(node.getLeft())+number(node.getRight())+1;
        }
        return 0;
    }



}


public class BST {
    public static void main(String[] args){
        BSTN b = new BSTN();
       while(b.number()<10000){
           b.non_insert((int)(Math.random()*(100000 - 1 +1)));
       }
         List l = new ArrayList();
       l.add(b.number());

        System.out.println("the BST number is : "+b.number()+"\n");
       for(int i=0;i<10;i++){
           int a=(int)(Math.random()*(100000 - 1 +1));
           System.out.println("the key is :"+a+"  "+b.non_query(a));
       }


    }
}












